package leetcode_500;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *SumII4_454 给定四个数组 寻找四个数组各取一个元素 和为0
 *describe:用hash记录两两 AC 80%
 *2018年8月24日 下午4:14:05
 */
public class SumII4_454 {
	
	/**
	 * describe:只用一个Hash  最优解 
	 * 2018年8月24日 下午4:11:05
	 */
	public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        int len=A.length;
       for(int i=0;i<len;i++){
           for(int j=0;j<len;j++){
               int sum=A[i]+B[j];
               map.put(sum,map.getOrDefault(sum,0)+1);
           }
       }
        int re=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                re+=map.getOrDefault(-C[i]-D[j],0);
            }
        }
        return re;
    }
	
	
	 /**
	 * describe:基础思想 双hash  AC 4%
	 * 2018年8月24日 下午4:10:42
	 */
	public int fourSumCount1(int[] A, int[] B, int[] C, int[] D) {
		   Map<Integer,Integer> map1=new HashMap<Integer,Integer>();
	       for(int i=0;i<A.length;++i) {
	    	   for(int j=0;j<A.length;++j) {
	    		   save(map1, A[i]+B[j]);
	    	   }
	       }
	       Map<Integer,Integer> map2=new HashMap<Integer,Integer>();
	       for(int i=0;i<A.length;++i) {
	    	   for(int j=0;j<A.length;++j) {
	    		   save(map2, C[i]+D[j]);
	    	   }
	       }
	       int res=0;
	       for(int key1:map1.keySet()) {
	    	   if(map2.containsKey(-key1)) {
	    		   res+=(map1.get(key1)*map2.get(-key1));
	    	   }
	       }
	       return res;
	 }
	 
	 public void save(Map<Integer,Integer> map,int num) {
		 Integer count=map.get(num);
		 if(count==null)
			 map.put(num,1);
		 else
			 map.put(num, count+1);
	 }
}
